/**
 * 带头结点的单链表
 */
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int E;
//定义结构体并取一个别名
typedef struct ListNode {
    E element;              //存放的元素值
    struct ListNode *next;  //下一个节点
} ListNode;
//给结构体指针取一个别名
typedef struct ListNode *Node;

/**
 * 初始化单链表
 * @param node 目标链表
 */
void initList(Node node) {
    node->next = NULL; //头结点默认下一个为NULL
}

/**
 * 链表插入元素
 * @param head 目标链表头节点
 * @param elem 需要插入的元素
 * @param index 插入的位置（注意顺序表的index是按位序计算的，从1开始，一般都是第index个元素）
 * @return 插入成功返回true，失败返回false
 */
_Bool insertElemToList(Node head, E elem, int index) {
    if (head == NULL || index < 1) return false;
    //寻找待插入节点的前驱节点并且限制index的上限
    while (--index) { //先自减后赋值
        head = head->next;
        if (head == NULL) return false;
    }
    //创建一个新的节点，用malloc函数分配内存空间保证局部变量node不被释放
    Node node = malloc(sizeof(ListNode));
    if (node == NULL) return false;
    node->element = elem;
    node->next = head->next;
    head->next = node;
    return true;
}

/**
 * 从单链表中删除指定位置的元素
 * @param head 目标链表头节点
 * @param index 要删除的位置索引
 * @return 删除成功返回true，失败返回false
 */
_Bool deleteElemFromList(Node head, int index) {
    if (head->next == NULL || index < 1) return false;
    //寻找待删除节点的前驱节点并且限制index的上限
    while (--index) { //先自减后赋值
        head = head->next;
        if (head == NULL || head->next == NULL) return false;
    }
    Node tmp = head->next;
    head->next = head->next->next;
    free(tmp);
    return true;
}

/**
 * 从单链表中获取指定位置元素
 * @param head 目标链表头节点
 * @param index 要获取的位置索引
 * @param e 获取到的数据
 * @return 获取成功返回true，失败返回false
 */
_Bool getElemFormList(Node head, int index, E *e) {
    if (head->next == NULL || index < 1) return false;
    //寻找待删除节点的前驱节点并且限制index的上限
    while (--index) { //先自减后赋值
        head = head->next;
        if (head == NULL || head->next == NULL) return false;
    }
    *e = head->next->element;
    return true;
}

/**
 * 查找单链表中指定元素的第一个出现的位置
 * @param head 目标链表头节点
 * @param elem 要查找的元素
 * @return 找到则返回第一个匹配的位置，未找到返回-1
 */
int locateElemFromList(Node head, E elem) {
    if (head->next == NULL) return -1;
    int i = 0;  //因为是带头结点的单链表第一个节点不存储数据，循环至少会执行一次，所以索引i初始值为0
    while (head) {
        if (head->element == elem) return i;
        ++i;
        head = head->next;
    }
    return -1;
}

/**
 * 打印单链表中的所有元素
 * @param head 目标链表头节点
 */
void printList(Node head) {
    while (head->next) {
        head = head->next;
        printf("%d ", head->element);   //因为头结点不存放数据，所以从第二个开始打印
    }
    printf("\n");
}

int main() {
    ListNode head;   //这里创建一个新的头结点，头结点不存放任何元素，只做连接，连接整个链表
    initList(&head);  //先进行初始化
    for (int i = 1; i < 8; ++i) {
        insertElemToList(&head, i, i);
    }
    printList(&head);
    insertElemToList(&head, 9, 6);
    printList(&head);
    deleteElemFromList(&head, 4);
    printList(&head);
    E e = 0;
    getElemFormList(&head, 4, &e);
    printf("%d \n", e);
    printf("%d \n", locateElemFromList(&head, 3));
    return 0;
}
